package common.advanced;

/**
 * @author ：Sei
 * @date ：Created in 2020/1/4 23:07
 * @description：树状数组
 * @modified By：
 * @version: $
 */
public abstract class AbstractBinaryIndexedTree<T> {

    protected int size;

    protected Object[] tree;

    protected AbstractBinaryIndexedTree(){}

    protected AbstractBinaryIndexedTree on(int size){
        this.size = size;
        return this;
    }

    //region 实例方法

    /**
     *
     * @param index
     * @param value
     * @param end
     */
    abstract public void update(int index, T value, int end);

    /**
     *
     * @param index
     * @param value
     */
    abstract public void update(int index, T value);

    /**
     *
     * @param index
     * @return
     */
    abstract public T query(int index);

    /**
     *
     * @param left
     * @param right
     * @return
     */
    abstract public T query(int left, int right);
    //endregion

    //region 静态方法

    /**
     * lowbit操作，非负整数二进制下最低位的1与后面的0组成的数值，如lowbit(101100)=(100)b=4
     * @param n
     * @return
     */
    protected static int lowbit(int n){
        return n & (~n+1);
    }
    //endregion

}
